import java.util.PriorityQueue;

class MedianFinder {

    // 创建大小根堆
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        this.maxHeap = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        this.minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
                maxHeap.offer(num);
            } else {
                minHeap.offer(num);
                // 更新大根堆和小根堆的元素数量
                maxHeap.offer(minHeap.poll());
            }
        } else {
            if (num <= maxHeap.peek()) {
                maxHeap.offer(num);
                // 更新大根堆和小根堆的元素数量
                minHeap.offer(maxHeap.poll());
            } else {
                minHeap.offer(num);
            }
        }
    }
    
    public double findMedian() {
        // 看数据流中的元素是奇数还是偶数
        int m = maxHeap.size();
        int n = minHeap.size();
        if ((m + n) % 2 == 1) { // 奇数
            // 取大根堆的堆顶值
            return maxHeap.peek();
        } else { // 偶数
            // 取大根堆和小根堆的堆顶，然后平均值
            return (maxHeap.peek() + minHeap.peek()) * 1.0 / 2;
        }
    }
}